home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / ELECTRON / 0989.ZIP / ESPRESSO.ARC / COMPL.C < prev    next >
Text File  |  1987-03-13  |  7KB  |  233 lines
  1. /*
  2.     module: compl.c
  3.     purpose: compute the complement of a multiple-valued function
  4.  
  5.     The "unate recursive paradigm" is used.  After a set of special cases
  6.     are examined, the function is split on the "most active variable".
  7.     These two halves are complemented recursively, and then the results
  8.     are merged.
  9. */
  10.  
  11. #include "espresso.h"
  12.  
  13. static compl_level = 0;
  14.  
  15.  
  16. /* complement -- compute the complement of T */
  17. pcover complement(T)
  18. INOUT pcube *T;         /* T will be disposed of */
  19. {
  20.     pcover Tbar;
  21.     register pcube cl, cr;
  22.     register int best;
  23.  
  24.     if (debug & COMPL)
  25.         debug_print(T, "COMPLEMENT", compl_level++);
  26.  
  27.     if (compl_special_cases(T, &Tbar) == MAYBE) {
  28.         if (cdata.vars_unate == cdata.vars_active)
  29.             best = unate_split_select(T, cl=new_cube(), cr=new_cube(), COMPL);
  30.         else
  31.             best = binate_split_select(T,cl=new_cube(), cr=new_cube(), COMPL);
  32.         Tbar = compl_merge(
  33.                    complement(scofactor(T, cl, best)),
  34.                    complement(scofactor(T, cr, best)), 
  35.                    cl, cr, best);
  36.         free_cubelist(T);
  37.     }
  38.  
  39.     if (debug & COMPL)
  40.         debug1_print(Tbar, "exit COMPLEMENT", --compl_level);
  41.     return Tbar;
  42. }
  43. bool compl_special_cases(T, Tbar)
  44. INOUT pcube *T;                 /* will be disposed if answer is determined */
  45. OUT pcover *Tbar;               /* returned only if answer determined */
  46. {
  47.     register pcube *T1, p, cof=T[0], temp=cube.temp[0], ceil=cube.temp[1];
  48.     pcover ceil_compl;
  49.  
  50.     /* Check for no cubes in the cover */
  51.     if (T[2] == NULL) {
  52.         *Tbar = sf_addset(new_cover(1), cube.fullset);
  53.         goto exit1;
  54.     }
  55.  
  56.     /* Check for only a single cube in the cover */
  57.     if (T[3] == NULL) {
  58.         *Tbar = compl_cube(set_or(temp, cof, T[2]));
  59.         goto exit1;
  60.     }
  61.  
  62.     /* Check for a row of all 1's (implies complement is null) */
  63.     for(T1 = T+2; (p = *T1++) != NULL; )
  64.         if (full_row(p, cof)) {
  65.             *Tbar = new_cover(0);
  66.             goto exit1;
  67.         }
  68.         
  69.     /* Check for a column of all 0's which can be factored out */
  70.     INLINEset_copy(ceil, cof);
  71.     for(T1 = T+2; (p = *T1++) != NULL; )
  72.         INLINEset_or(ceil, ceil, p);
  73.     if (! setp_equal(ceil, cube.fullset)) {
  74.         /* Factor out the cube "ceil" */
  75.         set_or(T[0], T[0], set_diff(temp, cube.fullset, ceil));
  76.         ceil_compl = compl_cube(ceil);
  77.         *Tbar = sf_append(complement(T), ceil_compl);
  78.         return TRUE;
  79.     }
  80.  
  81.     /* Collect column counts, determine unate variables, etc. */
  82.     massive_count(T);
  83.  
  84.     /* If single active variable not factored out above, then tautology ! */
  85.     if (cdata.vars_active == 1) {
  86.         *Tbar = new_cover(0);
  87.         goto exit1;
  88.     }
  89.         
  90.     /* Not much we can do about it */
  91.     return MAYBE;
  92.  
  93. exit1:
  94.     free_cubelist(T);
  95.     return TRUE;
  96. }
  97. /*
  98.     compl_merge -- merge the two cofactors around the splitting variable
  99.  
  100.     The merge operation involves intersecting each cube of the left
  101.     cofactor with cl, and intersecting each cube of the right cofactor
  102.     with cr.  The union of these two covers is the merged result.
  103.  
  104.     In order to reduce the number of cubes, a distance-1 merge is
  105.     performed (note that two cubes can only combine distance-1 in the
  106.     splitting variable).  Also, a simple expand is performed in the
  107.     splitting variable (simple implies the covering check for the
  108.     expansion is not full containment, but single-cube containment).
  109. */
  110.  
  111. pcover compl_merge(L, R, cl, cr, var)
  112. IN pcover L, R;
  113. IN register pcube cl, cr;
  114. IN int var;
  115. {
  116.     register pcube p, last, pt;
  117.     register pcover Tbar;
  118.     pcube *L1, *R1;
  119.  
  120.     /* Intersect each cube with the cofactored cube */
  121.     foreach_set(L, last, p)
  122.         INLINEset_and(p, p, cl);
  123.     foreach_set(R, last, p) {
  124.         INLINEset_and(p, p, cr);
  125.         SET(p, ACTIVE);
  126.     }
  127.  
  128.     /* Sort the arrays for a distance-1 merge */
  129.     set_copy(cube.temp[0], cube.var_mask[var]);
  130.     qsort((char *) (L1 = sf_list(L)), L->count, sizeof(pset), d1_order);
  131.     qsort((char *) (R1 = sf_list(R)), R->count, sizeof(pset), d1_order);
  132.  
  133.     compl_d1merge(L1, R1);
  134.     compl_lift(L1, R1, cr, var);
  135.     compl_lift(R1, L1, cl, var);
  136.     mem_free((char *) L1); 
  137.     mem_free((char *) R1);
  138.  
  139.     /* Re-create the merged cover */
  140.     Tbar = new_cover(L->count + R->count);
  141.     pt = Tbar->data;
  142.     foreach_set(L, last, p) {
  143.         INLINEset_copy(pt, p);
  144.         Tbar->count++;
  145.         pt += Tbar->wsize;
  146.     }
  147.     foreach_active_set(R, last, p) {
  148.         INLINEset_copy(pt, p);
  149.         Tbar->count++;
  150.         pt += Tbar->wsize;
  151.     }
  152.         
  153.     free_cover(L); 
  154.     free_cover(R);
  155.     free_cube(cl); 
  156.     free_cube(cr);
  157.     return Tbar;
  158. }
  159.  
  160.  
  161. /*
  162.     compl_d1merge -- distance-1 merge in the splitting variable
  163. */
  164. void compl_d1merge(L1, R1)
  165. IN register pcube *L1, *R1;
  166. {
  167.     register pcube pl, pr;
  168.  
  169.     /* Find equal cubes between the two cofactors */
  170.     for(pl = *L1, pr = *R1; (pl != NULL) && (pr != NULL); )
  171.         switch (d1_order(L1, R1)) {
  172.             case 1:
  173.                 pr = *(++R1); break;            /* advance right pointer */
  174.             case -1:
  175.                 pl = *(++L1); break;            /* advance left pointer */
  176.             case 0:
  177.                 RESET(pr, ACTIVE);
  178.                 INLINEset_or(pl, pl, pr);
  179.                 pr = *(++R1);
  180.         }
  181. }
  182.  
  183.  
  184. /*
  185.     compl_lift -- simple expand in the splitting variable
  186. */
  187. void compl_lift(A1, B1, bcube, var)
  188. IN pcube *A1, *B1, bcube;
  189. IN int var;
  190. {
  191.     register pcube a, b, *B2, lift = cube.temp[4], liftor = cube.temp[5];
  192.     pcube mask = cube.var_mask[var];
  193.  
  194.     (void) set_and(liftor, bcube, mask);
  195.  
  196.     /* for each cube in the first array ... */
  197.     for(; (a = *A1++) != NULL; )
  198.         if (TESTP(a, ACTIVE)) {
  199.  
  200.             /* create a lift of this cube in the merging coord */
  201.             (void) set_merge(lift, bcube, a, mask);
  202.  
  203.             /* for each cube in the second array */
  204.             for(B2 = B1; (b = *B2++) != NULL; ) {
  205.                 INLINEsetp_implies(lift, b, /* when_false => */ continue);
  206.  
  207.                 /* cube of A1 was contained by some cube of B1 */
  208.                 INLINEset_or(a, a, liftor);
  209.                 break;
  210.             }
  211.         }
  212. }
  213.  
  214.  
  215. /* compl_cube -- return the complement of a single cube (De Morgan's law) */
  216. pcover compl_cube(p)
  217. register pcube p;
  218. {
  219.     register int var;
  220.     register pcube temp = cube.temp[7], pdest, mask;
  221.     pcover R = new_cover(cube.num_vars);
  222.  
  223.     for(var = 0; var < cube.num_vars; var++) {
  224.         mask = cube.var_mask[var];
  225.         if (! setp_implies(mask, p)) {
  226.             pdest = GETSET(R, R->count++);
  227.             INLINEset_and(temp, p, mask);
  228.             INLINEset_diff(pdest, cube.fullset, temp);
  229.         }
  230.     }
  231.     return R;
  232. }
  233.